package main

import (
	"fmt"
)

/*
322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

*/

/*
硬币找零问题类似于爬楼梯问题，
	爬楼梯有两种step，硬币找零有 n 种 coin。
	爬楼梯问的是有多少种走法，硬币找零问题问的是哪种方法找零的个数最少。
把所有的走法都列出来，统计出最少的方法就行了。
用动态规划，从一开始就统计下每到达一步所需要的最好步数

动态规划表达式：
	f(i)表示到该步的最少步数
动态规划方程：
f(i) = min{f(i-coins[j])+1}  coins[j]为i之前的能一步走到i的位置

*/

func coinChange(coins []int, amount int) int {
	f := make([]int, amount+1)
	for i := range f {
		if i == 0 {
			f[i] = 0
			continue
		}
		f[i] = amount + 1

		for _, coin := range coins {
			if i >= coin {
				f[i] = min(f[i], f[i-coin]+1)
			}
		}
	}

	if f[amount] > amount {
		return -1
	}

	return f[amount]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	coins := []int{1, 2, 5}
	amount := 11
	fmt.Println(coinChange(coins, amount))
}
